#ifndef __BINARYLINKTREE_H_
#define __BINARYLINKTREE_H_
#define ElementType void*

class BinaryLinkTree
{
public:

    BinaryLinkTree();
    ~BinaryLinkTree();
    /* 调用插入函数 */
    void Insert(ElementType element);
    /* 调用删除函数 */
    void Remove(ElementType element);
    /* 调用查找函数 */
    ElementType * FindNode(ElementType element);

    void show();

    void SetShowtype(void(*showPtr)(ElementType));

private:
    struct  Node
    {
        Node(ElementType element)//不用进行封装，直接放在构造函数中
        {
            data = element;
            left = right = parent = nullptr;
        }
        ElementType data;
        Node *left;//左孩子
        Node *right;//右孩子
        Node *parent;//双亲节点
    };
    

    /* 插入节点 */
    Node * InsertNode(Node * node,ElementType element);
    /* 删除节点 */
    Node * RemoveNode(Node * node,ElementType element);
    /* 找到最小的节点 */
    Node * GetMinNode(Node * node);
    /* 查找函数 */
    ElementType * FindNode(Node * node,ElementType element);
    
/* ………………遍历输出……………… */
    /* 前序遍历 */
    void PrevTravel(Node * node,void(*showPtr)(ElementType));
    /* 中序遍历 */
    void MidTravel(Node * node,void(*showPtr)(ElementType));
    /* 后序遍历 */
    void PostTravel(Node * node,void(*showPtr)(ElementType));

    /* 求高度 */
    int GetNodeHeight(Node * node);
    /* 判断是否平衡 */
    int LeftRightDeviation(Node * node);
    
/* ………………失衡旋转……………… */
    /* 左旋 */
    Node * RotateLeft(Node * node);
    /* 右旋 */
    Node * RotateRight(Node * node);
    /* 左右旋 */
    Node * RotateLeftRight(Node * node);
    /* 右左旋 */
    Node * RotateRightLeft(Node * node);

    void (*showPtr)(ElementType); 
    
    Node * root;//成员变量
};

using BLTree = BinaryLinkTree;//不能放在上面，因为类之前还不认识它

#endif